
#ifndef BIGNUM_H
#define BIGNUM_H
#include "BigNum.h"
#include <vector>
void LongNum::SetVal(char* in)
{
    LongNum tmp(in);
    operator=(tmp);
}

LongNum::LongNum()
{
    data = new byte[DefSize];
    length = DefSize;
    sign = 1; // +
    nol=0;
}




LongNum::LongNum(const int in)
{
    data = new byte[5];
    length = 5;
    long t;
    if(in<0) {t=-in;} else {t=in;}
    for (int i=0; i<5; i++)
    {
        data[i]=t%100;
        t/=100;
    }
    if (in<0) sign = -1; else sign = 1;
    nol=0;
    RemoveZeros();
}
LongNum::LongNum(uint in)
{
	length = in;
	data = new byte[in];
	for( uint i =0; i<in;i++)
		data[i]='0';
        sign=1;
        nol=0;
}
LongNum::LongNum(char *in)
{
    uint s=strlen(in);
    if ( in[0]=='-' ) { sign=-1; s--; } else sign=1;
    if ( s%2==0 ) length=s/2; else length=s/2+1;
    data = new byte[length];
    memset(data,0,length);
    uint i=0;
    //char a,b;
    if (s>1){
        if (sign==-1) s++;
        for (i=0; i<=s-2; i+=2)
        {
            data[i/2] =(in[s-i-2]-48)*10 + (in[s-i-1]-48); // caienu n eiioa 48='0'//isdigit
        }
    }
    if ( i==s-1 )
        {
                if (in[s-1-i]=='-') s++;
                data[i/2]=in[s-1-i]-48;
        }
    nol=0;
//    RemoveZeros();
}




LongNum::LongNum(const LongNum &a)
{
    length=a.length;
    data= new byte[length];
    memcpy(data,a.data,length);
    sign=a.sign;
    nol=a.nol;
}




LongNum& LongNum::operator=(const LongNum &a)
{
    if (length!=a.length)
    {
        delete[] data;
        length=a.length;
        data = new byte[length];
    }
    memcpy(data,a.data,length);
    sign=a.sign;
    return *this;
}




byte& LongNum::operator[](const uint index)
{
    if ( index<length ) return data[index];     //return *(data+index)
    else return nol; // return nol
}

bool LongNum::operator ==(const int &a)
{
    LongNum tmp(a);
    return operator==(tmp);
}


bool LongNum::operator==(LongNum &a)
{
    uint beg;
    if ( length>a.length ) beg=length; else beg=a.length;
    for(int i=beg; i>=0; i--)
    {
        if(operator[](i)!=a[i]) return false;
    }
    if (sign!=a.sign) return false;
    return true;
}




bool LongNum::operator!=(LongNum &a)
{
    return (!(operator==(a)));
}




bool LongNum::operator<(LongNum &a)
{
    bool res=true;
    if (sign==a.sign)
    {
        if (length==a.length)
        {
            if (sign==-1) res=false;
            for (int i=length-1; i>=0; i--)  //aicii?ii ia io?ii -1
            {
                if (operator[](i)>a[i]) return !res;
                if (operator[](i)<a[i]) return res;
            }
            return false; // ?enea ?aaiu
        }
        else
        if (length<a.length) return res;
        else return !res;
    }
    else
    if (sign<a.sign) return true;
    else return false;
}




bool LongNum::operator<=(LongNum &a)
{
    bool res=true;
    if (sign==a.sign)
    {
        if (length==a.length)
        {
            if (sign==-1) res=false;
            for (int i=length-1; i>=0; i--)  //aicii?ii ia io?ii -1
            {
                if (operator[](i)>a[i]) return !res;
                if (operator[](i)<a[i]) return res;
            }
            return true; // ?enea ?aaiu
        }
        else
        if (length<a.length) return res;
        else return !res;
    }
    else
    if (sign<a.sign) return true;
    else return false;
}




bool LongNum::operator>(LongNum &a)
{
    bool res=true;
    if (sign==a.sign)
    {
        if (length==a.length)
        {
            if (sign==-1) res=false;
            for (int i=length-1; i>=0; i--)  //aicii?ii ia io?ii -1
            {
                if (operator[](i)>a[i]) return res;
                if (operator[](i)<a[i]) return !res;
            }
            return false; // ?enea ?aaiu
        }
        else
        if (length<a.length) return !res;
        else return res;
    }
    else
    if (sign>a.sign) return true;
    else return false;
}




bool LongNum::operator>=(LongNum &a)
{
    bool res=true;
    if (sign==a.sign)
    {
        if (length==a.length)
        {
            if (sign==-1) res=false;
            for (int i=length-1; i>=0; i--)
            {
                if (operator[](i)>a[i]) return res;
                if (operator[](i)<a[i]) return !res;
            }
            return true; // ?enea ?aaiu
        }
        else
        if (length<a.length) return !res;
        else return res;
    }
    else
    if (sign>a.sign) return true;
    else return false;
}




LongNum LongNum::operator-()
{
    LongNum tmp(*this);
    tmp.sign=-tmp.sign;
    return tmp;
}




LongNum LongNum::operator+(LongNum &a)
{
    LongNum tmp;
    tmp=operator +=(a);
    operator=(tmp);
    return *this;
}




LongNum LongNum::operator-(LongNum &a)
{
    LongNum tmp;
    tmp=operator -=(a);
    operator=(tmp);
    return *this;
}




LongNum LongNum::operator*(LongNum &a)
{
    LongNum tmp(*this);
    tmp*=a;
    return tmp;
}

LongNum LongNum::operator^(LongNum &a)
{
    LongNum tmp(*this);
    tmp^=a;
    return tmp;
}

LongNum module (LongNum &_number,LongNum &_degree,LongNum &_module)
{
    vector<bool> _Binary;
    _Binary=_degree.DegreeBinary();
    //if(_module==0) _module=LLONG_MAX;
    int size=_Binary.size();
    LongNum cur(1);
    for(int i=size-1;i>=0;i--)
    {
            cur*=cur;
            cur%=_module;
            if(_Binary[i])
                    cur=(cur*_number)%(_module);
            if(cur==0)
            {LongNum tmp(0);
            return tmp;}
    }
    return cur;
}


LongNum &LongNum::operator+=(LongNum &a)
{
    LongNum tmp(*this);
    if (sign<a.sign) { tmp=-tmp; return a-=tmp;}
    if (sign>a.sign) { a=-a; return tmp-=a;}
    if (sign==a.sign)
    {
        uint maxl;
        if (length>a.length) maxl=length; else maxl=a.length;
        delete[] data;
        data = new byte[maxl];
        memset(data,0,maxl);
        memcpy(data,tmp.data,length);
        length=maxl;
        uint i=0;
        byte atmp=0;
        byte perenos=0;
        for (i=0; i<maxl; i++)
        {
            atmp=operator[](i)+a[i]+perenos;
            data[i]=atmp%100;
            perenos=atmp/100;
        }
        if (perenos>0)
        {
            delete[] tmp.data;
            tmp.data = new byte[maxl+1];
            memset(tmp.data,0,maxl+1);
            memcpy(tmp.data,data,maxl);
            tmp.data[maxl]=perenos;
            tmp.length=maxl+1;
            operator =(tmp);
        }
/*        for(i=i; i<a.length; i++)
            data[i]+=a.data[i]; //=*/
    }
    return *this;
}




LongNum &LongNum::operator-=(LongNum &a)
{
    if ( operator==(a) ) return (*this=LongNum(0));
    LongNum tmp(*this);
    if ( sign==1 && a.sign==-1 ) { return tmp+=a;}
    if ( sign==-1 && a.sign==1 ) {tmp=-tmp; return tmp+=a;}
    uint i=0;
    int atmp=0;
//    byte perenos=0;
    if ( operator>=(a) )
    {
        for (i=0; i<length; i++)
        {
            atmp=operator[](i)-a[i];
            if ( atmp<0 )
            {
                //data[i+1]--;
                uint j=i;
                while(data[i+1]==0) i++;
                {
                    //if (i+1==length-1 && data[i+1]==1) length--;
                    data[i+1]--;
                }
                for(i=i; i>j; i--) data[i]+=100;
                atmp+=100;
            }
            data[i]=atmp%100;
        }
    }
    else
    {
        tmp=a-tmp;
        tmp.sign=-tmp.sign;
        operator=(tmp);
        i=tmp.length;
    }
    i--;
    /*while (data[i]==0)
    {i--;}
    if (i!=length)
    {
        delete[] tmp.data;
        tmp.data = new byte[length-i-1];
        tmp.length = length-i-1;
        memcpy(tmp.data,data,tmp.length);
        operator=(tmp);*/
        RemoveZeros();
        return *this;
 //   }
 //   else
   //     return *this;
}




LongNum &LongNum::operator*=(LongNum &a)
{
    uint s=length+a.length;
    byte *tmp = new byte[s];
    memset(tmp,0,s);
    uint i=0;
    uint j=0;
    uint atmp=0;
    byte perenos=0;
    for(i=0; i<length; i++)
    {
        for(j=0; j<a.length; j++)
        {
            atmp=data[i]*a.data[j]+perenos;
            tmp[i+j]=atmp%100+tmp[i+j];
            //if (tmp[i+j]>=100) {tmp[i+j+1]+=1; tmp[i+j]%=100;}
            perenos=atmp/100;
        }
        if( perenos!=0 ) {tmp[i+j]+=perenos; perenos=0;}
    }
    if( tmp[s-1]==0 ) s--;
    delete[] data;
    length=s;
    data = new byte[length];
    memcpy(data,tmp,length);
    delete[] tmp;
    if (sign==-1 && a.sign==-1) sign=1;
    if (sign!=a.sign) sign=-1;
    for (i=0; i<length; i++)
        if (data[i]>=100)
        {data[i+1]+=data[i]/100; data[i]%=100;}
    return *this;
}

vector <bool> LongNum::DegreeBinary ()
{
        vector <bool> Binary;
        LongNum _degree;
        _degree=(*this);
        while (!(_degree==0))
        {
                if ((_degree%2)==1)
                        Binary.push_back(true);
                else
                        Binary.push_back(false);
                _degree=(_degree)/2;
        }
        return Binary;
}

LongNum &LongNum::operator^=(LongNum &_degree)
{
        vector<bool> _Binary;
        _Binary=_degree.DegreeBinary();
        int size=_Binary.size();
        LongNum cur(1);
        for(int i=size-1;i>=0;i--)
        {
                cur=(cur*cur);
                if(_Binary[i])
                        cur=operator*=(cur);
                if(cur==0)
                        {LongNum tmp(0);
                        return tmp;}
        }
        return cur;
}





LongNum::~LongNum()
{
    if(data)
    delete[] data;
}




ostream &operator<<(ostream &stream, LongNum &a)
{
    if (a.sign==-1) stream<<"-";
    for (uint i=a.length-1; i>0; i--)
    {
        char b;
        b=char(a.data[i]/10+48);
        if (b!='0')
        stream<<char(a.data[i]/10+48);
        stream<<char(a.data[i]%10+48);
    }
    stream<<char(a.data[0]/10+48)<<char(a.data[0]%10+48);
//    a.RemoveZeros();
    return stream;
}




istream &operator>>(istream &stream, LongNum &a)
{
    char *in=NULL;
    stream >> in;
    a=LongNum(in);
    return stream;
}




byte* LongNum::GetVal()
{
    byte *tmp;
    uint s;
    if (char(data[length-1]/10+48)=='0'){s=length*2-1;}
    else {s=length*2;}
    tmp = new byte[s];
    memset(tmp,0,s);
    uint i=s-1;
    for (uint j=0; j<length; j++ )
    {
        if(!(s%=2)||j!=length-1)
        tmp[i-1]=(char)(data[j]/10+48); //i
        tmp[i]=(char)(data[j]%10+48);   //i-1
        i-=2;
    }
    tmp[i]=(char)(data[0]%10+48);   //i-1
    tmp[i-1]=(char)(data[0]/10+48); //i
    return tmp;
}




uint LongNum::GetLength()
{
    uint s=0;
    if (char(data[length-1]/10+48)=='0')s=length*2-1;
    else s=length*2;
    return s;
}


void LongNum::RemoveZeros()
{
    uint i=length-1;
    while (data[i]==0&&i!=0)
    {i--;}
    if (i!=length-1 &&i!=0)
    {
        LongNum tmp;
        length = length-i-1;
        tmp.length=length;
        memcpy(tmp.data,data,length);
        operator=(tmp);
    }
    if (i==0)
    {
        byte *tmp = new byte[1];
        memcpy(tmp,data,1);
        delete[] data;
        length=1;
        data = new byte[1];
        memcpy(data,tmp,1);
    }
}

bool LongNum::GetSign()
{
    if(sign==1) return true;
    else return false;
}
LongNum& LongNum::LDiv(LongNum& l1,const LongNum& l2)
{
	LongNum tmp = l1;
        if(l1.length<l2.length) { LongNum res((uint)1); return res; }
	LongNum* l_res = new LongNum(l1.length-l2.length);
	LongNum tmp2 =LongNum(l1.length);
	for(uint i=0; i<l2.length;i++)
                        tmp2.data[tmp2.length-i-1]=l2.data[l2.length-i-1]; //added -1
        for (uint i=l_res->length;i>0;i--)
        {
                LongNum zero(0);
                while(l1-tmp2 >zero)
		{
                        l_res->data[i-1]++;
		}
	}
	l_res->RemoveZeros();
	return *l_res;
}
LongNum& LongNum::LMod(LongNum& l1, LongNum& l2)
{
	if(l1.length<l2.length) return l1;
        LongNum tmp;
        tmp=LDiv(l1,l2);
        tmp*=l2;
        tmp=l1-l2;
        LongNum* l_res = new LongNum(tmp);
        return *l_res;
}
LongNum LongNum::operator %(LongNum &a)
{
	return LMod(*this,a);
}

LongNum& LongNum::operator %=(LongNum &a)
{
	return LMod(*this,a);
}

LongNum& LongNum::operator /=(LongNum &a)
{
	return LDiv(*this,a);
}	

LongNum LongNum::operator /(LongNum &a)
{
	return LDiv(*this,a);
}
LongNum LongNum::operator/(const int &a)
{
        return LDiv(*this,LongNum(a));
}
LongNum LongNum::operator%(const int &a)
{
    LongNum tmp(a);
    return LMod(*this,tmp);
}
#endif
